Leetcode Day 2
问题主要在怎么判断 4 和 9。
想到一位一位读,
或者每次读到 特殊位置的时候就做判断,比如 读到
不,这样效率太低,感觉模拟人类可能算是比较好的方法了。
那么关键在于:如何从右往左读字符,以及怎么判断什么时候加什么时候减:好像每次读取都必须要判断。
ai建议我切片,以及:
是的,你在倒着遍历字符串时,可以通过几种方法同时获取当前字符和上一次(即原始字符串中它右边的那个)字符。没有一个直接的内建函数能一步到位,但以下是几种优雅且常用的方法:
方法一:使用 zip 配合切片 (推荐,通用性好)
这是利用 zip 函数将两个序列对应元素打包成元组的特性。我们将反转后的字符串与其去掉第一个字符的版本进行 zip。
my_string = "hello"
reversed_s = my_string[::-1] # "olleh"
# reversed_s -> o, l, l, e, h
# reversed_s[1:] -> l, l, e, h
# zip 将配对 (o,l), (l,l), (l,e), (e,h)
# 在循环中,current 是当前字符,previous 是上一个处理的(即原字符串中右边的)
for current_char, previous_char in zip(reversed_s, reversed_s[1:]):
print(f"Current: {current_char}, Previous: {previous_char}")
# 在这里你可以同时访问 current_char 和 previous_char
# 比如检查 current_char 是否和 previous_char 构成特定模式
# 输出:
# Current: o, Previous: l
# Current: l, Previous: l
# Current: l, Previous: e
# Current: e, Previous: h
# 注意:这个方法不会处理反转后的第一个字符 'o',因为它没有“上一个”字符。
# 如果你需要单独处理第一个字符(即原字符串的最后一个字符),可以在循环外进行:
if my_string: # 确保字符串不为空
first_char_in_reverse = reversed_s[0]
print(f"Processing the first reversed character separately: {first_char_in_reverse}")
# ... 对 first_char_in_reverse 的处理 ...
方法二:手动记录上一个字符 (最直观)
在循环中用一个变量显式地存储上一次迭代的字符。
my_string = "hello"
previous_char = None # 或者其他哨兵值,表示初始状态没有上一个字符
for i, current_char in enumerate(my_string[::-1]):
if i == 0:
print(f"Processing first reversed char: {current_char} (No previous)")
# 对第一个字符的特殊处理(如果需要)
else:
print(f"Current: {current_char}, Previous: {previous_char}")
# 在这里同时访问 current_char 和 previous_char
# 在循环的末尾更新 previous_char,供下一次迭代使用
previous_char = current_char
# 输出:
# Processing first reversed char: o (No previous)
# Current: l, Previous: o
# Current: l, Previous: l
# Current: l, Previous: e
# Current: e, Previous: h
previous_char 变量。方法三:使用 itertools.pairwise (Python 3.10+,最优雅)
如果你的 Python 版本是 3.10 或更高,itertools 模块提供了一个完美的工具 pairwise。
import itertools
my_string = "hello"
# pairwise(iterable) 返回一个迭代器,产生 (elem[0], elem[1]), (elem[1], elem[2]), ...
# 我们对反转后的字符串使用它
reversed_s = my_string[::-1] # "olleh"
# pairwise(reversed_s) -> ('o', 'l'), ('l', 'l'), ('l', 'e'), ('e', 'h')
for current_char, previous_char in itertools.pairwise(reversed_s):
print(f"Current: {current_char}, Previous: {previous_char}")
# 输出:
# Current: o, Previous: l
# Current: l, Previous: l
# Current: l, Previous: e
# Current: e, Previous: h
# 同样,这个方法不包含反转后的第一个字符 'o' 的单独处理,
# 因为 pairwise 需要至少两个元素才能产生一对。
# 如果需要处理第一个字符,可以在循环前单独进行:
if my_string:
first_char_in_reverse = reversed_s[0]
print(f"Processing the first reversed character separately: {first_char_in_reverse}")
# ...
方法四:使用索引 (手动,但能访问索引)
如果你确实需要知道当前字符在原始字符串中的索引(尽管在倒序遍历时通常不直接需要),可以用 range 来倒序遍历索引。
my_string = "hello"
n = len(my_string)
# 倒序遍历索引: n-1, n-2, ..., 1 (不包括 0)
# 因为我们要访问 i+1,所以循环到 1 即可
for i in range(n - 1, 0, -1):
current_char = my_string[i] # 当前字符 (索引 i)
previous_char = my_string[i - 1] # 上一个字符 (索引 i-1, 这是原字符串中左边的)
# 注意:这里的 previous_char 是原字符串中左边的!
# 如果你要的是倒序遍历中“上一个”处理的字符 (即原字符串右边的)
# 那么应该是:
current_char_in_reverse_pass = my_string[i]
previous_char_in_reverse_pass = my_string[i+1] # 需要处理 i = n-1 的边界情况
# --- 修正为符合题目要求的版本 ---
my_string = "hello"
n = len(my_string)
if n > 0:
# 先处理反转后的第一个字符 (原字符串最后一个)
first_rev_char = my_string[n-1]
print(f"Processing first reversed char: {first_rev_char} (Index {n-1})")
# 再处理剩下的,索引从 n-2 到 0
for i in range(n - 2, -1, -1):
current_char = my_string[i] # 当前字符 (索引 i)
previous_char_processed = my_string[i+1] # 上一次处理的字符 (索引 i+1)
print(f"Current: {current_char} (Index {i}), Previous Processed: {previous_char_processed} (Index {i+1})")
# 输出:
# Processing first reversed char: o (Index 4)
# Current: l (Index 3), Previous Processed: o (Index 4)
# Current: l (Index 2), Previous Processed: l (Index 3)
# Current: e (Index 1), Previous Processed: l (Index 2)
# Current: h (Index 0), Previous Processed: e (Index 1)
总结推荐:
itertools.pairwise(my_string-1) 是最优雅的。zip(reversed_s, reversed_s[1:]) 非常 Pythonic 且兼容性好。选择哪种方法取决于你的 Python 版本、代码风格偏好以及是否需要对第一个(反转后的)字符进行特殊处理。
这题很简单,不知道为什么你能做这么久。
练习了try 和 except 的使用,大概知道是怎么一回事了。
# 2. 遍历列表中 *其余* 的字符串(从第二个开始)。
for i in range(1, len(strs)):
这里可以优化。
此外ai说每次加char的效率不如用list然后最后join起来,因为str不可变。有道理。
数组中有重复数字,应该用hash表存起来吧?
好像又没必要
每三个都判断是否互不相同,然后看和是不是 0?可以更优化吗?
应该每个组合都拿出来看看。那就看吧。三重循环。
实际编写的时候很多概念都不知道,比如两个列表什么时候相等?顺序是影响的。那么要么排序,但是我总觉得python有更好的办法。
好的,如果你希望比较两个列表,只关心它们包含的元素种类和数量是否完全相同,而不考虑元素的排列顺序,有以下几种常用且 Pythonic 的方法:
方法一:使用 collections.Counter (推荐,适用于可哈希元素)
这是最直接、最能表达“元素及其计数相同”意图的方法。collections.Counter 是一个特殊的字典子类,用于计算可哈希对象(如数字、字符串、元组)的频率。
from collections import Counter
list1 = [1, 2, 3, 2, 1]
list2 = [3, 1, 2, 1, 2]
list3 = [1, 2, 3] # 数量不同
list4 = [1, 1, 1, 2, 3] # 1 的数量不同
# Counter 会统计每个元素出现的次数
counter1 = Counter(list1) # Counter({1: 2, 2: 2, 3: 1})
counter2 = Counter(list2) # Counter({1: 2, 2: 2, 3: 1})
counter3 = Counter(list3) # Counter({1: 1, 2: 1, 3: 1})
counter4 = Counter(list4) # Counter({1: 3, 2: 1, 3: 1})
print(f"list1 vs list2 (Counter): {counter1 == counter2}") # 输出: True
print(f"list1 vs list3 (Counter): {counter1 == counter3}") # 输出: False
print(f"list1 vs list4 (Counter): {counter1 == counter4}") # 输出: False
Counter(list) 会创建一个字典,其中键是列表中的唯一元素,值是该元素在列表中出现的次数。然后,直接比较这两个 Counter 对象 (counter1 == counter2)。如果它们的键值对完全相同(即包含相同的元素,并且每个元素的计数也相同),则结果为 True。方法二:排序后比较 (适用于可排序元素)
如果两个列表包含相同的元素且数量也相同,那么将它们排序后,得到的列表必定完全相等。
list1 = [1, 2, 3, 2, 1]
list2 = [3, 1, 2, 1, 2]
list3 = [1, 2, 3]
list4 = [1, 1, 1, 2, 3]
# sorted() 函数返回一个新的排好序的列表
sorted_list1 = sorted(list1) # [1, 1, 2, 2, 3]
sorted_list2 = sorted(list2) # [1, 1, 2, 2, 3]
sorted_list3 = sorted(list3) # [1, 2, 3]
sorted_list4 = sorted(list4) # [1, 1, 1, 2, 3]
print(f"list1 vs list2 (sorted): {sorted_list1 == sorted_list2}") # 输出: True
print(f"list1 vs list3 (sorted): {sorted_list1 == sorted_list3}") # 输出: False (长度不同,所以肯定不等)
print(f"list1 vs list4 (sorted): {sorted_list1 == sorted_list4}") # 输出: False (排序后内容不同)
sorted() 函数分别对两个列表进行排序(注意 sorted() 返回新列表,不修改原列表),然后使用标准的列表相等比较 (==) 来比较这两个排序后的列表。Counter 慢。< 或 > 运算)。如果列表包含无法互相比较的类型(如混用数字和字符串),sorted() 会报错。为什么不能直接比较 set?
你可能会想到用 set(list1) == set(list2)。但这是错误的,因为它忽略了元素的数量/频率。set 只关心元素是否存在,不关心它出现了多少次。
list1 = [1, 1, 2]
list2 = [1, 2, 2]
print(set(list1)) # 输出: {1, 2}
print(set(list2)) # 输出: {1, 2}
print(set(list1) == set(list2)) # 输出: True (错误!因为元素数量不同)
print(Counter(list1) == Counter(list2)) # 输出: False (正确)
print(sorted(list1) == sorted(list2)) # 输出: False (正确)
总结推荐:
collections.Counter,它语义最清晰且通常效率最高。sorted() 后比较也是一个很好的选择。Dataview (inline field '='): Error:
-- PARSING FAILED --------------------------------------------------
> 1 | =
| ^
Expected one of the following:
'(', 'null', boolean, date, duration, file link, list ('[1, 2, 3]'), negated field, number, object ('{ a: 1, b: 2 }'), string, variable
我们这里可以使用set,因为里面的内容物是不同的,不过发现list还有sorted函数?
好的,我们来详细探讨 Python 列表的 sorted() 函数,并比较在确定列表元素唯一时,使用 set 和 sorted 进行内容相等性检查的效率。
sorted(list)sorted() 是 Python 的一个内建函数 (built-in function),它接收一个可迭代对象 (iterable) 作为主要参数(列表 list 是最常见的可迭代对象之一),并返回一个新的、排好序的列表 list。
关键特性:
返回新列表: 这是 sorted() 最重要的特性之一。它不会修改原始的可迭代对象(比如你传入的列表),而是创建一个全新的、包含排序后元素的列表。这与列表自身的 list.sort() 方法不同,list.sort() 是原地排序,直接修改列表本身,并且返回 None。
my_list = [3, 1, 4, 1, 5, 9, 2]
original_id = id(my_list)
# 使用 sorted()
sorted_list = sorted(my_list)
print(f"Original list: {my_list}") # 输出: Original list: [3, 1, 4, 1, 5, 9, 2] (未改变)
print(f"Sorted list: {sorted_list}") # 输出: Sorted list: [1, 1, 2, 3, 4, 5, 9] (新列表)
print(f"Original list ID same? {id(my_list) == original_id}") # 输出: True
print(f"Sorted list is new? {id(sorted_list) != original_id}") # 输出: True
print("-" * 10)
# 使用 list.sort()
my_list.sort() # 原地排序
print(f"Original list after sort(): {my_list}") # 输出: Original list after sort(): [1, 1, 2, 3, 4, 5, 9] (已改变)
print(f"Original list ID same after sort()? {id(my_list) == original_id}") # 输出: True
输入: 可以接受任何可迭代对象,如列表、元组、字符串、集合、字典(默认排序键)、字典的 .keys(), .values(), .items() 视图等。
print(sorted((5, 1, 3))) # 输入元组 -> 输出列表: [1, 3, 5]
print(sorted("hello")) # 输入字符串 -> 输出列表: ['e', 'h', 'l', 'l', 'o']
print(sorted({3, 1, 4})) # 输入集合 -> 输出列表: [1, 3, 4]
print(sorted({'b': 1, 'a': 2})) # 输入字典 -> 输出排序后的键列表: ['a', 'b']
输出: 无论输入是什么类型的可迭代对象,sorted() 总是返回一个新的列表。
排序顺序:
<, > 等运算符)。数字按数值大小排,字符串按字典序(字母顺序)排。TypeError。
# print(sorted([3, "a", 1])) # 会引发 TypeError: '<' not supported between instances of 'str' and 'int'
可选参数: sorted() 函数接受两个非常有用的可选关键字参数:
key: 指定一个函数,这个函数会在排序比较之前作用于可迭代对象中的每一个元素。排序将根据这个函数返回的键 (key) 来进行,而不是直接比较原始元素。这对于自定义排序逻辑非常强大。
words = ["apple", "Banana", "Cherry", "date"]
# 默认排序 (区分大小写)
print(sorted(words))
# 输出: ['Banana', 'Cherry', 'apple', 'date']
# 按小写字母排序 (不区分大小写)
print(sorted(words, key=str.lower))
# 输出: ['apple', 'Banana', 'Cherry', 'date']
# 按长度排序
print(sorted(words, key=len))
# 输出: ['date', 'apple', 'Banana', 'Cherry'] (长度相同时保持原相对顺序,因为 Timsort 是稳定的)
data = [('Alice', 25), ('Bob', 20), ('Charlie', 20)]
# 按年龄 (元组第二个元素) 排序
print(sorted(data, key=lambda item: item[1]))
# 输出: [('Bob', 20), ('Charlie', 20), ('Alice', 25)] (注意 Bob 和 Charlie 维持了原相对顺序)
reverse: 一个布尔值。如果设置为 True,则按降序 (Descending Order) 排列。默认为 False (升序)。
nums = [3, 1, 4, 1, 5]
print(sorted(nums, reverse=True))
# 输出: [5, 4, 3, 1, 1]
排序算法: Python 的 sorted() (和 list.sort()) 使用 Timsort 算法。Timsort 是一种混合、稳定的排序算法,结合了归并排序和插入排序的优点。它对部分有序的数据表现特别好。
稳定性 (Stability): Timsort 是稳定的。这意味着如果多个元素具有相同的键(或者在不使用 key 参数时它们本身相等),它们在排序后的输出列表中的相对顺序将与它们在原始输入可迭代对象中的顺序保持一致。这在多级排序或需要保持原始顺序的情况下很有用(如上面按长度排序和按年龄排序的例子)。
复杂度:
set vs sorted 检查内容相等性(元素唯一)现在,我们来看你的特定问题:如果你确定一个列表 list 里的元素都是不同的(唯一的),并且你想检查两个这样的列表 list1 和 list2 是否包含完全相同的元素(不考虑顺序),使用 set 转换后比较和使用 sorted 转换后比较,哪个效率更高?
场景:
list1, list2 包含的元素保证是唯一的。list1 和 list2 是否是相同元素的集合(忽略顺序)。方法一:使用 set
result = set(list1) == set(list2)
set(list1): 遍历 list1,将每个元素添加到哈希表中构建集合 set1。由于元素唯一,这个过程主要是哈希计算和插入。平均时间复杂度 O(N)。set(list2): 同上,构建集合 set2。平均时间复杂度 O(N)。set1 == set2: 比较两个集合是否相等。这通常需要比较它们的长度,然后逐个检查一个集合中的元素是否存在于另一个集合中(利用哈希表的 O(1) 平均查找)。对于等长集合,比较的时间复杂度平均为 O(N)。方法二:使用 sorted
result = sorted(list1) == sorted(list2)
sorted(list1): 对 list1 进行排序(如 Timsort)。时间复杂度 O(N log N)。sorted(list2): 对 list2 进行排序。时间复杂度 O(N log N)。sorted_list1 == sorted_list2: 比较两个排好序的列表是否相等。这需要逐个元素比较。时间复杂度 O(N)。效率比较结论:
在平均情况下,对于检查元素唯一的两个列表是否包含相同的内容(忽略顺序):
set (O(N)) 通常比使用 sorted (O(N log N)) 效率更高。这是因为哈希表的平均 O(1) 查找和插入通常比排序所需的 O(N log N) 比较操作要快。
但是,请注意以下几点:
set 方法。如果元素不可比较(如混合了不兼容类型),则不能使用 sorted 方法。sorted 的实际运行时间可能因为常数因子较小而与 set 差不多甚至更快。但随着列表规模 N 的增大,O(N) 的渐近优势会越来越明显。总结推荐 (元素唯一时):
set(list1) == set(list2),因为它在理论上和实践中通常都更快、更直接地反映了“集合内容是否相等”的意图。sorted(list1) == sorted(list2)。并且添加的时候可以用这样的方法:
好的,你想在向列表 append 元素时,确保只有当这个元素不在列表中时才添加,从而避免重复。这里有几种常用的方法,各有优劣:
方法一:每次添加前检查 (if item not in list) - 最直观
这是最直接的想法,也易于理解。
my_list = [10, 20, 30]
items_to_add = [20, 40, 10, 50]
for item in items_to_add:
if item not in my_list: # 检查元素是否已存在
my_list.append(item)
print(f"已添加: {item}")
else:
print(f"已存在,跳过: {item}")
print(f"最终列表: {my_list}")
# 输出:
# 已存在,跳过: 20
# 已添加: 40
# 已存在,跳过: 10
# 已添加: 50
# 最终列表: [10, 20, 30, 40, 50]
item not in my_list 操作需要遍历列表来查找元素。对于列表,这个查找的时间复杂度是 O(N),其中 N 是列表当前的长度。如果你需要频繁地进行这种“检查并添加”的操作,并且列表变得很长,那么整体效率会比较低(可能接近 O(M*N),M 是你要添加的元素数量)。方法二:使用集合 (set) 辅助进行快速查找 - 效率更高
如果你需要进行大量的添加操作,并且关心效率,可以同时维护一个集合 (set) 来快速判断元素是否存在。集合的查找操作平均时间复杂度是 O(1)。
my_list = [10, 20, 30]
# 创建一个包含列表初始元素的集合,用于快速查找
existing_items_set = set(my_list)
items_to_add = [20, 40, 10, 50]
for item in items_to_add:
# 在集合中检查是否存在 (O(1) 平均时间)
if item not in existing_items_set:
my_list.append(item) # 添加到列表 (保持顺序)
existing_items_set.add(item) # 也添加到集合 (用于后续快速查找)
print(f"已添加: {item}")
else:
print(f"已存在 (通过 set 检查),跳过: {item}")
print(f"最终列表: {my_list}")
print(f"最终集合: {existing_items_set}")
# 输出:
# 已存在 (通过 set 检查),跳过: 20
# 已添加: 40
# 已存在 (通过 set 检查),跳过: 10
# 已添加: 50
# 最终列表: [10, 20, 30, 40, 50]
# 最终集合: {10, 20, 30, 40, 50}
item not in existing_items_set 非常快 (O(1))。my_list 中元素的原始添加顺序。方法三:最终结果使用集合去重(如果顺序不重要或可以后处理)
如果你不关心元素的添加顺序,或者可以在所有元素添加完之后再处理顺序和去重,可以直接先全部添加(或使用集合),最后再转换。
# 情况 A: 如果最终顺序无所谓,可以直接用集合
my_list = [10, 20, 30]
items_to_add = [20, 40, 10, 50]
# 直接将两者合并到集合中,自动去重
final_set = set(my_list) | set(items_to_add) # 使用集合的并集操作
# 或者
# final_set = set(my_list)
# final_set.update(items_to_add)
print(f"最终集合 (顺序丢失): {final_set}") # 输出: {10, 20, 30, 40, 50} (顺序可能不同)
# 如果需要列表形式
final_list_no_order = list(final_set)
print(f"最终列表 (顺序丢失): {final_list_no_order}")
# 情况 B: 如果需要保持原始列表顺序,并添加新元素(去重)
my_list = [10, 20, 30]
items_to_add = [20, 40, 10, 50]
existing_items_set = set(my_list) # 记录已存在的
for item in items_to_add:
if item not in existing_items_set:
my_list.append(item)
existing_items_set.add(item) # 同样需要更新 set
print(f"最终列表 (保持顺序): {my_list}") # [10, 20, 30, 40, 50]
方法四:利用字典的键保持插入顺序 (Python 3.7+)
从 Python 3.7 开始(CPython 3.6 就已经是了),字典会保持其键的插入顺序。我们可以利用这个特性来模拟一个“有序集合”。
my_list = [10, 20, 30]
items_to_add = [20, 40, 10, 50]
# 使用字典的键来存储元素,值可以任意(比如 None 或 True)
# 初始元素放入字典
ordered_unique_dict = {item: None for item in my_list}
for item in items_to_add:
# 尝试添加,如果键已存在,字典会自动处理(保持第一次插入的位置)
if item not in ordered_unique_dict:
print(f"已添加: {item}")
else:
print(f"已存在,跳过: {item}")
ordered_unique_dict[item] = None # 添加或更新键
# 最后从字典的键获取有序的、唯一的元素列表
final_list = list(ordered_unique_dict.keys())
print(f"最终列表: {final_list}")
# 输出:
# 已存在,跳过: 20
# 已添加: 40
# 已存在,跳过: 10
# 已添加: 50
# 最终列表: [10, 20, 30, 40, 50]
总结推荐:
if item not in my_list) 最简单明了。set 操作(方法三 A)最简洁。根据你的具体需求(列表大小、添加频率、是否需要保持顺序、元素类型)来选择最合适的方法。
然而列表不能 Hash。要不全部转成 set? 这样,单独开一个 Hash来记录进来的元素好了
不不不,核心在于 set 和 list 都放不到 set 里面。
原来python中还有元组这个数据类型,那应该好办了。
???怎么相等还能输出的?
原来不是值相等啊,无敌了,怎么读的题????
寄,我觉得优化挺好啊。那就只能一开始就hash掉试试。
整个换思路:
一开始就hash,然后取
答案是可以把 dict.keys 转成列表。
哎。真是太烂了。